กรอบการทำงานทางอัลกอริธึม
โซลูชันเชิงตัวเลขสร้าง ลำดับที่ลดค่าลง: ลำดับของจุด $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$ โดยที่ $f(x^{(k)}) \to p^*$ เมื่อ $k \to \infty$ แต่ละขั้นตอนอัปเดตตำแหน่งผ่าน $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$ โดยที่ $\Delta x$ เป็นทิศทางที่ลดลง
วิธีการที่กล่าวไว้ในบทนี้ต้องการจุดเริ่มต้นที่เหมาะสม $x^{(0)}$ จุดเริ่มต้นต้องอยู่ใน $\text{dom } f$ และนอกจากนี้ เซตย่อยระดับ $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ ต้องเป็นเซตปิด ซึ่งช่วยให้มั่นใจได้ว่าลำดับจะคงอยู่ในบริเวณที่มีพฤติกรรมดี ที่เมทริกซ์ฮีสเซียนให้ข้อมูลที่มีประโยชน์
ทิศทางที่ง่ายที่สุดคือ $\Delta x = -\nabla f(x)$. อย่างไรก็ตาม ประสิทธิภาพมักต้องคำนึงถึงรูปทรงเรขาคณิตที่แตกต่างกันผ่าน ทิศทางการลดลงที่ดีที่สุด:
- มาตรฐานกำลังสอง: $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$.
- $L_\infty$ นอร์ม: $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ (การลดลงตามพิกัด)
โมเดลลำดับที่สองและเขตเชื่อมั่น
วิธีนิวตันใช้การประมาณการเทย์เลอร์ลำดับที่สอง: $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ พาราโบล่าจะถูกลดค่าต่ำสุดเมื่อ $v = \Delta x_{nt}$ (ก้าวของนิวตัน) เราจะนิยาม เขตเชื่อมั่น: เซต $\{v \mid \|v\|_2 \le \gamma\}$. พารามิเตอร์ $\gamma$ สะท้อนความมั่นใจของเราในโมเดลลำดับที่สอง เมื่อโมเดลมีความแม่นยำ เราจะหาทิศทางผ่าน $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ ในระบบที่เคเคที
- ขอบเขตความไม่เหมาะสม: $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$ ถูกต้องหาก $\lambda(x) < 1$
- ผลรวมความสมมาตรเอง: หาก $f_1, f_2$ เป็นความสมมาตรเอง แล้ว $f_1 + f_2$ ก็จะเป็นความสมมาตรเอง
- ความเบาบางของเมทริกซ์ฮีสเซียน: ประสิทธิภาพจะเพิ่มขึ้นหาก เงื่อนไขโครงสร้างแถบของเมทริกซ์ฮีสเซียน: $\nabla^2 f(x)_{ij} = 0$ เมื่อ $|i-j| > k$ เป็นจริง